import java.io.*;
import java.sql.Date;
import java.sql.Time;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.ArrayList;
import java.util.Collections;


/* 
 * Sourabh Jain; sourj@cs.umn.edu
 * World for the viro simulations
 */
public class World {
	/*
	 * BellMan ford section starts
	 */

	public final int INF = Integer.MAX_VALUE;

	// this class represents an edge between two nodes
	class Edge {
		int source; // source node
		int destination; // destination node
		int weight; // weight of the edge
		public Edge() {}; // default constructor
		public Edge(int s, int d, int w) { source = s; destination = d; weight = w; }
	}

	/*
	 * BellMan ford section ends
	 */	

	Hashtable<Long, Set<Long>> topo;  
		/* 
		 * It stores the set of physical neighbors for all the nodes (vid), 
		 * It only stores the vids.
		 */
		List<Message> msgQueue; 
		/* 
		 * a queue to handle messages, and provide communication between a node and the world
		 */
		int tickCounter = 0; 
		/* time*/
		
		int nnodes; 
		/* total number of nodes in the topology*/
		
		Hashtable <Long, Boolean> nodestatus; 
		/* if the node is live or dead*/
		
		//Hashtable<Long , Location> locations; 
		/* location of each node, location could be simply x,y coordinates of each point.*/
		
		float radius;
		/* 
		 * Communication range of each node, e.g. if it is 
		 * a wireless topology, then it means that a given node 
		 * can communicate with all the nodes in this radius directly.
		 */ 
		
		Hashtable <Long,Node> node;
		/*
		 * Nodes in the network, each node is represented as an object of the class
		 * Node 
		 */
		
		int lbit; 
		/*
		 *  length of the virtual id space, e.g. if it 
		 *  is an l-bit id space then value of lbit = l
		 */
		
		Hashtable<Long, Long>uid2vid;
		Hashtable<Long, Long>vid2uid;
		
               /*
		* This contains the shortest path length between all nodes.
		*/
		int[][] minHopTable  ;
                /*
		 * This contains the path information between any two nodes. 
		 */
                String[][] path; 
                /*
		 *This contains the lsa receipt information .
		 * ArrayList tells the list of nodes for which lsa information is received.
                 */    
		Hashtable<Integer, ArrayList<Integer>>lsa_receipt;
               /*
		*Number of LSA packets processed by each node. 
    	        */   
		Hashtable<Integer, Integer>countLSA;
               /*
		* Number of nodes in the topology. This is important in case of fraction
		*/
                int nodes_count;
                /*
		 * List of UID of all the valid nodes.
		 */  
		ArrayList<Integer> nodeList;
		
		int currentRoutingRoundNumber = 0;
		
		public static boolean debug = false;
		String topofile = "";
		/*
		public boolean computeStretch = false;
		public boolean recordPairWisePaths = false;
		public boolean recordRoutingTables = false;
		public boolean recordRoutingTables_ospf = true;
		public boolean recordPairWisePaths_ospf = false;
		public boolean fillMinHopTable_run = true;
		public boolean run_viro = false;
		public float fracDrop = 0.0f;
		public double seed = 0;
		*/


	public boolean computeStretch = false;
	public boolean recordPairWisePaths = false;
	public boolean recordRoutingTables = true;
	public boolean recordRoutingTables_ospf = false;
	public boolean recordPairWisePaths_ospf = false;
	public boolean recordControlPacketCount = true;// set it to true if we want to measure the viro control overhead
	public boolean countPackets = false; // set it to false if we want to measure the viro control overhead
	public boolean fillMinHopTable_run = false;
	public boolean run_viro = true;
	public boolean plottopology = false;
	public boolean run_lsa = false;
	public float fracDrop = 0.0f;
	public double seed = 0;
	public String opt = "";

	List <String> loops;
	ArrayList<Long> allVids;
	/* 
	 * a queue to handle messages, and provide communication between a node and the world
	 */

	
	public World (String topofile, String vidmapfile,  String configfile, String opt)  {
		/*
		 * constructor for the world
		 * 1. read the topology file and initialize the variables.
		 * 2. read the vidmapfile and initialize the required variables.
		 * frac: specifies how many edges to drop
		 */

		/*
		 * Initialize the variables:
		 */
		getConfiguration (configfile);
		this.topofile = topofile.substring(topofile.lastIndexOf("/")+1);
		//this.topofile = topofile.replace("/", "_");
		println("Outputfile names: "+this.topofile, true);
		topo = new Hashtable<Long, Set<Long>> ();
		uid2vid = new Hashtable<Long, Long> ();
		vid2uid = new Hashtable<Long, Long> ();
		node  = new Hashtable<Long, Node>();
		msgQueue = new LinkedList<Message>();
		loops = new LinkedList<String>();
		this.opt = opt;
		/*SAURABH's JOB */

		if(fillMinHopTable_run )fillMinHopTable(topofile, opt);
		/*
		 * Fill the minHopTable using the "bellmanford/dijsktra's" algorithm.
		 */
		//minHopTable = getShortestHopDistance(topo);

		//1. open the topology file.
		Scanner in_topofile = null;
		Scanner in_vidmapfile = null;

		try{
			in_topofile = new Scanner(new File(topofile));
			in_vidmapfile = new Scanner(new File(vidmapfile));
		}catch(Exception e){
			e.printStackTrace();
			System.exit(0);
		}
		// Now first get the mapping
		/*
		 * File will look like as shown below
		 *  <uid> <white space> <vid>
		 *  1 2
		 *  2 8
		 *  3 9
		 *  ...
		 */
		long uid,vid;
		long largestvid = -1;
		allVids = new ArrayList<Long>();
		while(in_vidmapfile.hasNextLong()){
			uid = in_vidmapfile.nextLong(); 
			vid = in_vidmapfile.nextLong();
			allVids.add(vid);
			uid2vid.put(uid, vid);
			vid2uid.put(vid, uid);
			topo.put(vid,new HashSet<Long>() );
			if(vid > largestvid){
				largestvid = vid;
			}
		}
		Collections.sort(allVids);
		in_vidmapfile.close();
		nnodes = uid2vid.keySet().size();
		lbit = Long.toBinaryString(largestvid).length();
		/*
		 * File will look like as shown below
		 *  <uid1> <white space> <uid2> <white space> <weight>
		 *  10 5 1
		 *  5 10 1
		 *  ...
		 */
		if (opt.equals("-g")){
			/*
			 * if the input is a graph file then ignore the first two intergers
			 * these integers correspond to number of vertices and edges in the graph.
			 * |E| |V|
			 */
			in_topofile.nextInt();
			in_topofile.nextInt();
		}
		long n1,n2; n1 = n2 = 0;
		Random generator = new Random();
		//Date d = new Date();
		//long time = System.currentTimeMillis();
		System.out.println("Seed time value is:"+Double.toString(seed));
		generator.setSeed((long) seed);
		//generator.
		while(in_topofile.hasNextLong()){
			n1 = in_topofile.nextInt();
			n2 = in_topofile.nextInt();
			if (generator.nextFloat() < fracDrop){
				continue;
			}
			if (!opt.equals("-g")){
				/*
				 * if the input is a graph file then we assume 
				 * that it is unweighted graph file. so there will be no 
				 * weight. else read the weight value.
				 */
				in_topofile.nextInt();
			}
			// now perform the uid2vid mapping
			println("uid2vid lookup for n1: "+n1,debug);
			n1 = uid2vid.get(n1);
			println("uid2vid lookup for n2: "+n2,debug);
			n2 = uid2vid.get(n2);

			// now insert n1 into n2's list, and n2 in n1's list
			topo.get(n1).add(n2);
			topo.get(n2).add(n1);
		}

		// Now create the nodes
		Set<Long> vidset = vid2uid.keySet();
		for (Iterator<Long> vidit = vidset.iterator(); vidit.hasNext();){
			vid = vidit.next();
			// now create a new node.
			//Node(int l, List<Message> queue, long uid, long vid, Set<Long> myNeighbors, World myworld)
			Node newnode = new Node(lbit, msgQueue, vid2uid.get(vid), vid, topo.get(vid),this);
			node.put(vid,newnode);
		}
		plotTopology();

	}		


	public void plotTopology() {
		// TODO Auto-generated method stub
		/*
		 * This function plots the topology using the function "dot"
		 */

		// task 1: first create a dot file.
		FileWriter fw;
		long x = System.currentTimeMillis();
		try {			
			fw = new FileWriter("temp/topo" + x + ".dot");
			fw.write("graph G {\n");
			Set<Long> vidset = vid2uid.keySet();
			Set<Long> viddone = new HashSet<Long>();
			for (Iterator<Long> vidit = vidset.iterator(); vidit.hasNext();){
				long vid = vidit.next();
				Set<Long> neighbors = topo.get(vid);
				for (Iterator<Long> n_it = neighbors.iterator(); n_it.hasNext();){
					long pn = n_it.next();
					if (viddone.contains(pn) == false){
						fw.write(""+World.toBinaryString(vid)+"--"+World.toBinaryString(pn)+";\n");
					}
				}
				viddone.add(vid);
			}
			fw.write("}\n");
			fw.close();
			//String command = "dot -Tpng -o temp/topo.png temp/topo" + x + ".dot ";
			//String command = "/usr/local/bin/neato -Tpng -o temp/topo.png temp/topo.dot";
			//Runtime.getRuntime().exec(command);

			//Runtime.getRuntime().exec("eog temp/topo.png");
			//Runtime.getRuntime().exec("/Applications/Preview.app/Contents/MacOS/Preview temp/topo.png");        

		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}
	public	void run () {
		/*
		 * This is a method that is invoked from the main method to start the 
		 * simulations.
		 * 1. construct the virtual id layer, if the vidmapfile is not provided
		 * 2. Based upon the topology, it will instantiate the node objects,
		 * 	  will initialize the buckets for these nodes.
		 * 3. then construct the routing tables for all the nodes by calling 
		 * 	  constructRoutingTable() method on a round by round basis for all the nodes
		 * 4. Next measure the stretch for all pairs o(unsigned long)f source 
		 *    destination and collect the desired statistics.
		 */

		// first print the intial routing tables of each node:
		
		int i = 0;
		/*for ( i  = 0; i < allVids.size(); i++){
			long vid1 = allVids.get(i);
			println("Current vid1 = "+vid1 + " ",true);
			if (node.containsKey(vid1)){
				println("Current vid1 = "+vid1 + " ",true);
			}
		}*/
		//println("Reached here as well: ", true);
		i = 1;
		boolean NodesRoutingTableIsChanging = true;
		if (run_viro) {
			//while ( i < lbit + 5 || NodesRoutingTableIsChanging == true){
			int maxiteration= lbit+3;
			//println("Reached here as well 1: ", true);
			while ( i < maxiteration){
				//for (int i = 1; i <= lbit+100; i++){
				currentRoutingRoundNumber = i;
				/*try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}*/
				//println("Reached here as well 2: ", true);
				System.out.print("\tCurrent iteration: "+i+" out of: "+(maxiteration));		
				println("\n--------------------------------------------------\nAfter "+i+"th round of routing table construction\n--------------------------------------------------\n",true);
				constructRoutingTables();
				NodesRoutingTableIsChanging = false;			
				int jj = 0;
				for ( jj  = 0; jj < allVids.size(); jj++){
					long vid1 = allVids.get(jj);
					if (node.containsKey(vid1)){
						println(node.get(vid1).toString(),true);
						NodesRoutingTableIsChanging = node.get(vid1).isRoutingTableChanged();
					}
				}
				println("\n\n--------------------------------------------------\n", true);		
				i++;

			}
			int jj = 0;
			for ( jj  = 0; jj < allVids.size(); jj++){
				long vid1 = allVids.get(jj);
				if (node.containsKey(vid1)){
					println(node.get(vid1).toString(),true);
					NodesRoutingTableIsChanging = node.get(vid1).isRoutingTableChanged();
				}
			}
		}
		System.out.println("Stopping after "+i+" iterations");
		/*
		 * Code for generating the stretch pairs:
		 * It will look as follows:
		 * src(vid) <space> dest(vid) <space> logical distance <space> physical dist <space> nhops <space> stretch
		 */
		if (recordControlPacketCount){
			countPackets = true;
			constructRoutingTables();
			try {
				FileWriter fw = new FileWriter(topofile+".control-overhead");
				fw.write("Uid VIROcontrolPacketCount\n");
				//println("Recording the results now:",true);
				int jj = 0;
				for ( jj  = 0; jj < allVids.size(); jj++){
					long vid1 = allVids.get(jj);
					if (node.containsKey(vid1)){
						//fw.write("node: "+ vid2uid.get(vid1)+"\n");
						fw.write(vid2uid.get(vid1)+ " "+ node.get(vid1).viroControlPacketCount+ "\n");
					}
				}	
				fw.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		if (recordRoutingTables){
			try {
				FileWriter fw = new FileWriter(topofile+".rt."+(fracDrop));
				int jj = 0;
				for ( jj  = 0; jj < allVids.size(); jj++){
					long vid1 = allVids.get(jj);
					if (node.containsKey(vid1)){
						//fw.write("node: "+ vid2uid.get(vid1)+"\n");
						fw.write(node.get(vid1).routing_table_toString() + "\n");
					}
				}	
				fw.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		println("WARNING: Currently commented out the function call Measure_LSAload ()", true);
		//Measure_LSAload();
		print_ctrlPckt();
		if(computeStretch){
			System.out.println(" Measuring stretch now!");
			measure_stretch();	
		}
		if(recordPairWisePaths ){
			System.out.println(" Recording pair wise paths!");	
			recordAllPairPaths();

		}
		if(recordPairWisePaths_ospf ){
			System.out.println(" Recording pair wise paths for OSPF!");	
			recordAllPairPaths_OSPF();
		}
		if (recordRoutingTables_ospf){
			recordRoutingTable_OSPF();
		}
	} 

	public void runLSACount() {
		if (run_lsa){
			try {
				int jj = 0;
				for ( jj  = 0; jj < allVids.size(); jj++){
					long vid1 = allVids.get(jj);
					if (node.containsKey(vid1)){
						//fw.write("node: "+ vid2uid.get(vid1)+"\n");
						node.get(vid1).startLsa();
					}
				}
				FileWriter fw = new FileWriter(topofile+".ospf.control-overhead");
				fw.write("NodeUid LSACount\n");
				jj = 0;
				for ( jj  = 0; jj < allVids.size(); jj++){
					long vid1 = allVids.get(jj);
					if (node.containsKey(vid1)){
						fw.write(vid2uid.get(vid1) + " "+ node.get(vid1).lsacount +"\n");
					}
				}	
				fw.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}


	public void recordAllPairPaths() {
		BufferedWriter bw = null;
		try {
			bw = new BufferedWriter(new FileWriter(this.topofile + ".paths"));
			bw.write("src(uid) dest(uid) pathlen path\n");
			for (long src = 0; src <= (1L<<lbit);src++){
				if (node.containsKey(src)){
					println("Recording paths for the source node (vid): " + src, true);
					//System.out.println(node.get(vid1).toString());
					int jj = 0;
					for ( jj  = 0; jj < allVids.size(); jj++){
						long dest = allVids.get(jj);
						if (node.containsKey(dest) && dest != src){
							Path path = new Path();
							Message msg = new Message();
							msg.src = src;
							msg.dest = dest;
							msg.type = Message.HOPCOUNT_PATH;
							msg.payload = path;
							routepacket(msg);
							String towrite = vid2uid.get(src) + " "+ vid2uid.get(dest) + " " + ((Path)msg.payload).pathlen + " "+ ((Path)msg.payload).path + "\n";
							bw.write(towrite);
							println(towrite,false);
							//Thread.sleep(100);
						}
					}
				}
				//Thread.sleep(10);
			}
			bw.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	public void recordAllPairPaths_OSPF(){
		println("Recording OSPF paths for the source node (vid): ", true);
		BufferedWriter bw = null;
		int pathlen = 0;
		try {
			bw = new BufferedWriter(new FileWriter(this.topofile + ".paths.ospf"));
			bw.write("src(uid) dest(uid) pathlen path\n");
			for (int src = 0; src < nodeList.size() ;src++){
				println("Recording OSPF paths for the source node (vid): " + src, true);
				pathlen = 0;
				for (int dest = 0; dest < nodeList.size(); dest++){	
					StringTokenizer tempStringTokenizer = new StringTokenizer(path[nodeList.get(src)][nodeList.get(dest)]);
					pathlen  = tempStringTokenizer.countTokens();
					String towrite = nodeList.get(src) + " " + nodeList.get(dest) + " " + (pathlen+1)  + (path[nodeList.get(src)][nodeList.get(dest)]).toString() + " " + nodeList.get(dest) + "\n";
					if (nodeList.get(src) != nodeList.get(dest) && pathlen != 0){
						bw.write(towrite);
						println(towrite,debug);
					}
				}
				//Thread.sleep(10);
			}
			bw.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
	}

	public void recordRoutingTable_OSPF(){

		println("Recording OSPF Routing Table for the nodes:", true);
		BufferedWriter bw = null;
		int pathlen = 0;
		String nextHop = "";
		try {
			bw = new BufferedWriter(new FileWriter(this.topofile + ".rt."+"ospf."+this.fracDrop ));
			for (int src = 0; src < nodes_count ;src++){
				String towrite;
				towrite = "RoutingTable at Node(UID): " + src + "\n";
				pathlen = 0;
				for (int dest = 0; dest < nodes_count; dest++){	
					if (src == dest)
						continue;
					if (nodeList.contains(src) && nodeList.contains(dest)){							
						StringTokenizer tempStringTokenizer = new StringTokenizer(path[src][dest]);
						pathlen  = tempStringTokenizer.countTokens();				
						if (pathlen > 0){
							tempStringTokenizer.nextToken();
							// PATHLEN =1 MEANS	THERE EXIST A DIRECT EDGE
							if (pathlen == 1){
								nextHop = Integer.toString(dest);
							}else{
								nextHop = tempStringTokenizer.nextToken();
							}
							towrite += "[" + dest + "]" + src + " " + dest + " " + nextHop + "\n";
						} else{
							towrite += "["+dest + "]\n";
						}						
					}else if (!nodeList.contains(src) || !nodeList.contains(dest)){
						towrite += "["+dest + "]\n";											
					}
				}
				towrite+="\n";
				bw.write(towrite);
				//println(towrite,true);
			}
			bw.close();
		}catch (Exception e) {
			e.printStackTrace();
		}									
	}

	public void measure_stretch() {
		BufferedWriter bw = null;
		int physical;
		try {
			bw = new BufferedWriter(new FileWriter(this.topofile + ".stretch"));
			bw.write("src(uid) dest(uid) logical_distance physical_distance nhops_using_viro stretch\n");
			int jj = 0;
			for ( jj  = 0; jj < allVids.size(); jj++){
				long src = allVids.get(jj);
				if (node.containsKey(src)){
					println("Measuring stretch with respect to node: " + src, true);
					//System.out.println(node.get(vid1).toString());
					int jjj = 0;
					for ( jjj  = 0; jjj < allVids.size(); jjj++){
						long dest = allVids.get(jjj);
						if (node.containsKey(dest) && dest != src){
							Message msg = new Message();
							msg.src = src;
							msg.dest = dest;
							msg.type = Message.HOPCOUNT;
							vid2uid.get(dest); vid2uid.get(src);
							int nhops = routepacket(msg);
							int logical = delta (src, dest);
							println("vids: src = "+src+" dest = "+dest+"\tuids: src = "+vid2uid.get(src)+" dest = "+vid2uid.get(dest),debug);
							//int physical = minHopTable [0][1];
							if (opt.compareTo("-g") == 0){
								if (nodeList.contains((vid2uid.get(dest)).intValue()-1) && nodeList.contains((vid2uid.get(src)).intValue()-1)){
									physical = minHopTable[(vid2uid.get(dest)).intValue()-1][(vid2uid.get(src)).intValue()-1] ;
								}else{
									physical = -1;
								}
							}else{
								if (nodeList.contains((vid2uid.get(dest)).intValue()) && nodeList.contains((vid2uid.get(src)).intValue())){
									physical = minHopTable[(vid2uid.get(dest)).intValue()][(vid2uid.get(src)).intValue()] ;
								}else{
									physical = -1;
								}
							}
							String towrite =src + " "+ dest +" " +logical + " " +physical + " "+nhops+" "+ (float)nhops/(float)physical+"\n" ; 		
							bw.write(towrite);
							print(towrite,debug);
							//Thread.sleep(100);
						}
					}
				}
			}
			bw.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}

	public void constructRoutingTables(){
		/*
		 * This function will perform the one round of routing table construction
		 */
		int jj = 0;
		for ( jj  = 0; jj < allVids.size(); jj++){
			long vid1 = allVids.get(jj);
			if (node.containsKey(vid1)){
				node.get(vid1).constructRoutingTable();
			}
		}
	}

	public void constructRoutingTables(int nrounds){
		/*
		 * This function runs multiple rounds of routing tables simultaneously
		 */
		for (int i = 0; i < nrounds; i++) {
			constructRoutingTables();
		}
	}

	// No references this method... Dead code
	public double vid_lookup(long uid){
		/*
		 * This function maps a uid to a vid
		 */
		return 0;	
	}

	public int routepacket(Message msg){
		/*
		 * This function "emulate" the routing of a packet from uid1 to uid2.
		 * It fist computes the shortest distance between any two nodes in 
		 * the physical topology.
		 * then it computes the # physical hops traveled when the packet is 
		 * routed using the routing tables at every node using the viro protocol
		 * Finally it reports the routing stretch, which is the ratio of (pathlen using viro)/shortest_pathlen
		 */

		/*
		 * PSEUDOCODE:
		 * using the next hop information try to reach the destination.
		 * stop and flip if corresponding bucket is empty, and move on.
		 */
		int hopcount = 0;
		long nexthop = 0;
		long src1 = msg.src;
		long dest1 = msg.dest;
		long currentnode = msg.src;
		long dest = msg.dest;
		boolean status = false;
		boolean recordpath = true;
		ArrayList<Long> pathvector = new ArrayList<Long>();
		List<Long> route = new LinkedList<Long>();
		route.add(msg.src);
		println("[RoutePacket: ]"+msg+"",debug);
		print ("[RoutePacket: ] currentnode -> "+currentnode+"",debug);
		while (currentnode != dest){
			if (msg.type == Message.HOPCOUNT_PATH){
				((Path)msg.payload).pathlen++;
				((Path)msg.payload).path= ((Path)msg.payload).path  + vid2uid.get(currentnode) + " ";
			}
			else if(recordpath){
				if (!pathvector.contains(currentnode))
					pathvector.add(currentnode);
				else if (pathvector.lastIndexOf(currentnode) != pathvector.size()-1){
					String loopis = pathvector+ " " +currentnode + "";
					if (!loops.contains(loopis)){
						loops.add(loopis);
						//println ("\n-->New loop: "+ loopis, true);
						//println("-->Oringinal: Routing loop, src: "+src1+"->"+currentnode+"->"+dest1,true);
						//println("-->After changes: Routing loop, src: "+msg.src+"->"+currentnode+"->"+msg.dest,true);
					}
					return -1; // there is a loop here. so destination should be unreachable.
				}
/*				else {
					String loopis = pathvector+ " " +currentnode + "";
					if (!loops.contains(loopis)){
						println ("Stupid loop: "+ loopis, true);
						loops.add(loopis);
					}
				}*/
			}
			int dist = delta(currentnode,dest);
			nexthop = getNextHop(currentnode, dest);
			if (node.get(currentnode).myNeighbors.contains(dest)){
				nexthop = dest;
			}
			hopcount ++;
			msg.ttl--;
			if (msg.ttl == 0){
				try {
					//println("\t-->Oringinal: Routing loop, src: "+src1+"->"+currentnode+"->"+dest1,debug);
					//println("\t-->After changes: Routing loop, src: "+msg.src+"->"+currentnode+"->"+msg.dest,debug);
					//println("\n\nATTENTION: Packet's TTL expired!! \nPacket was: "+msg+"\n\n\n",debug);
					//println("Here is the loop: "+ pathvector.toString(),debug);
					/*if (currentRoutingRoundNumber > 27){
						System.out.println("Routing tables for the source node: "+ node.get(msg.src));
						System.out.println("Routing tables for the source node: "+ node.get(currentnode));
					}*/
					//Thread.sleep(1000);
				} catch (Exception e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				return -1;
			}
			//print("-> "+nexthop,debug);
			if (nexthop == -1){
				long mask = 1;
				dest = dest ^ (mask << (dist-1));
				continue;
			}

			currentnode = nexthop;
			route.add(currentnode);
		}
		println("\n",debug);
		//println("\n\n"+msg+"",countPackets);
		//println("PATH VECTOR:: "+pathvector, countPackets);
		//println("Currentnode is::"+currentnode,countPackets);
		if (((msg.type == Message.RDV_PUBLISH || msg.type == Message.RDV_QUERY|| msg.type == Message.RDV_REPLY) && msg.ttl > 5) && countPackets){
			Iterator<Long> nodesOnPath = pathvector.iterator();
			//println("Now incrementing the packet counts",true);
			while (nodesOnPath.hasNext()){
				long nodenext = nodesOnPath.next();
				node.get(nodenext).viroControlPacketCount++;
				//println("Incrementing the count at node: "+nodenext+" New count is: "+node.get(nodenext).viroControlPacketCount,true);
			}
		}
		// Now see, what is the packet type.
		if (msg.type == Message.RDV_PUBLISH){
			status =  (publish(msg,currentnode));
		}
		else if (msg.type == Message.RDV_PUBLISH_PREFIX){
			status =  (publishPrefix(msg,currentnode));
		}
		else if (msg.type == Message.RDV_QUERY){
			status =  (query_new(msg,currentnode));
		}
		else if (msg.type == Message.RDV_BRIDGE_QUERY){
			status =  (query_bridge_new(msg,currentnode,route));
		}
		else if (msg.type == Message.HOPCOUNT){
			if (dest == msg.dest){
				status = true;
			}else{
				status = false;
			}
		}
		else if (msg.type == Message.HOPCOUNT_PATH){
			//((Path)msg.payload).pathlen++;
			((Path)msg.payload).path= ((Path)msg.payload).path  + vid2uid.get(currentnode) + " ";
			if (dest == msg.dest){
				status = true;
			}else{
				status = false;
			}
		}
		// returns the hopcount if the status is true,
		// else it will return -1 
		hopcount = (status == false? -1:hopcount); 
		return hopcount;
	}

	public boolean publishPrefix(Message msg, long currentnode) {
		//(Set<Prefix>) msg.payload;
		Iterator<Prefix> prefix_it = ((Set<Prefix>) msg.payload).iterator();
		int level = (Integer)msg.payload1;
		while (prefix_it.hasNext()){
			Prefix new_pfix = prefix_it.next();
			if(node.get(currentnode).prefixtable.get(level)==null){
				System.out.println("node.get(currentnode).prefixtable.get(level) is null!!"+"\nLevel: "+level);
				System.out.println("Currentnode: "+currentnode+" Prefix is: "+new_pfix+" ID is: "+new_pfix.prefix);
			}
			node.get(currentnode).prefixtable.get(level).add(new_pfix);
		}	
		return true;
	}

	// Used but redundant
	public void print(String string, boolean debug) {
		// TODO Auto-generated method stub
		if (debug == true){
			System.out.print(string);
		}

	}
	public static void println(String string, boolean debug) {
		// TODO Auto-generated method stub
		if (debug == true){
			System.out.println(string);
		}

	}
	
	
	// Dead code
//	public boolean routePacketLogically(Message msg){
		/*
		 * This function will route a message using the 
		 * logical relationships.
		 * 
		 * Therefore, it doesn't require any physical connections to be set up.
		 */

		/*
		 * This function will first try to go to the destination or a node which is closest to the destination.
		 * currentnode = src;
		 * while (currentnode != dest){
		 * 		dist = delta(currentnode, dest);
		 * 		nextlogicalhop = node[currentnode-1].buckets[dist].dest 
		 * 		if (nextlogicalhop == -1){
		 * 			//break;
		 * 			It means there is a hole at this level, therefore We should try to reach a node which is 
		 * 			closest to the destination rendezvous id.  
		 * 			Hence, instead of breaking here and coming out of the loop, we will try to reach a node which 
		 * 			is the closest to the destination (using the XOR measure), and we go to a later bucket. 
		 * 
		 * 		}
		 * 		currentnode = nextlogicalhop;
		 * }
		 */		
	/*	long nextLogicalhop = 0;
		long currentnode = msg.src;
		long dest = msg.dest;
		//System.out.println("PacketTrace:\n"+"MessageType: "+msg.getType()+": "+msg.src + " -> "+ msg.dest + " ("+(Bucket)msg.payload+")");
		//System.out.print("Path: "+currentnode);
		// while we don't reach the destination node
		while (currentnode != dest){
			// compute the logical distance between the current node 
			// and the destination so that we can pick the appropriate
			// bucket.
			int dist = delta(currentnode,dest);
			// see the corresponding bucket information
			//nextLogicalhop = node.get(currentnode).buckets[dist].dest;
			nextLogicalhop = getLogicalNext(currentnode, dest);
			if (nextLogicalhop == -1){
				// flip the bit here, and go for a smaller bucket now
				long mask = 1;
				dest = dest ^ (mask << (dist-1));
				continue;
			}
			currentnode = nextLogicalhop;
			//System.out.print(" -> "+currentnode);
		}
		//System.out.println();

		//Have reached the destination or a node closest to the destination.

		//Now see, what is the packet type.
		if (msg.type == Message.RDV_PUBLISH){
			return (publish(msg,currentnode));
		}
		else if (msg.type == Message.RDV_QUERY){
			return(query(msg,currentnode));
		}
		else if (msg.type == Message.RDV_BRIDGE_QUERY){
			return(query_bridge(msg,currentnode));
		}
		return true;
	}
	*/
	
	public long getLogicalNext(long currentnode, long dest) {
		// This function selects "any" of the next logical in the 
		// corresponding bucket and returns it
		Set<Bucket> options = node.get(currentnode).buckets.get(delta(currentnode,dest));
		return longestPrefixMatch(options, dest).dest;
	}
	
	/*
	// Dead code
	public boolean query_bridge(Message msg, long currentnode) {
		// Now you have reached the "rendezvous point"

		// the bucket_level at the destination (or the rendezvous point) will
		// be same as the distance between the node which made the query and 
		// the destination node itself.
		int bucket_level = delta(msg.src, currentnode);
		// Now go through all the buckets to find a match.
		for (Iterator<Bucket> it = node.get(currentnode).rendezvousStore.iterator(); it.hasNext();) {
			Bucket b1 = it.next();
			// see if this is the desired bucket by comparing the bucket_level.
			if (b1.bucket_level == bucket_level){
				// Now see if the destination node is at the distance
				// from the msg.src which is same as msg.payload.bucket_level
				if (delta(msg.src, b1.dest) == ((Bucket)(msg.payload)).bucket_level){
					Bucket b = new Bucket();
					b.bridge[0] = b1.gw;
					b.bridge[1] = b1.dest;
					b.gw = msg.src;
					b.dest = b1.dest;
					b.prefix = ((Bucket)(msg.payload)).prefix;
					//b.nexthop = node.get(msg.src).buckets[delta(msg.src,msg.dest)].nexthop;
					b.nexthop = getNextHop (msg.src, msg.dest);
					b.bucket_level = ((Bucket)(msg.payload)).bucket_level;
					node.get(msg.src).buckets.add(b);
					return true;
				}
			}
		}
		return false;
	}
	*/
	
	public boolean query_bridge_new(Message msg, long currentnode,List<Long> route) {
		// Now you have reached the "rendezvous point"

		// the bucket_level at the destination (or the rendezvous point) will
		// be same as the distance between the node which made the query and 
		// the destination node itself.
		int bucket_level = delta(msg.src, currentnode);
		// Now go through all the buckets to find a match.
		Set <Bucket> options = new HashSet<Bucket>();
		for (Iterator<Bucket> it = node.get(currentnode).rendezvousStore.iterator(); it.hasNext();) {
			Bucket b1 = it.next();
			// see if this is the desired bucket by comparing the bucket_level.
			if (b1.bucket_level == bucket_level){
				// Now see if the destination node is at the distance
				// from the msg.src which is same as msg.payload.bucket_level
				
				if (delta(msg.src, b1.dest) == ((Bucket)(msg.payload)).bucket_level){
					Bucket b = new Bucket();
					b.gw = b1.gw;
					b.dest = b1.dest;
					b.prefix = ((Bucket)(msg.payload)).prefix;
					if(msg.src == b1.gw){
						b.nexthop = b1.nexthop;
					} else{
						b.nexthop = getNextHop (msg.src, b1.gw);
					}
					b.bucket_level = ((Bucket)(msg.payload)).bucket_level;
					options.add(b);
					println("Added option bucket: "+b,debug);
					//node.get(msg.src).buckets.add(b);
					//return true;
				}
			}
		}
		if (options.isEmpty() == false){
			/*TASK 1*/
			// Install the best match in the nodes routing table
			Bucket best = new Bucket();
			best.copyFrom(getLogicallyClosest(options,msg.src));	
			println("Best option is: "+best,debug);
			//best.copyFrom(getOne(options));
			// Why adding in the buckets instead of adding in the actual bucketset routing table?
			node.get(msg.src).buckets.add(best);
			/*TASK 2*/
			// update the prefixtable in the routing table of the rdv point node.
			
			Prefix p1 = new Prefix();
			Prefix p2 = new Prefix();
			p1.prefix = msg.src;
			p2.prefix = best.dest;
			p1.maxlen = lbit;
			p2.maxlen = lbit;
			p1.len = p2.len = getCommonPrefixLen (p1.prefix, p2.prefix)+1;
			node.get(currentnode).prefixtable.get(delta(p1.prefix,currentnode)).add(p1);
			node.get(currentnode).prefixtable.get(delta(p2.prefix,currentnode)).add(p2);
			println("At node: "+currentnode+" Adding prefixes: \n"+p1+"\n"+p2,debug);

			/* 
			 * Now check IF any node on the route should INSTALL new PREFIXES or not. 
			 * This is done by doing the following check
			 * if there is some x in route such that delta(x,src) > delta(src,dest)
			 * Then x should install a new prefix.
			 */
			Iterator<Long> route_it = route.iterator();
			long routenode=route_it.next();
			int dist1 = delta(msg.src, best.dest);
			while (route_it.hasNext()){
				routenode = route_it.next();
				//if (dist1 < delta(msg.src,routenode)){

				println("Current routing node is: "+routenode+"\nAnd the route is: "+route+"\nSrc is: "+msg.src, debug);
				// add the new prefixes
				try{
					//if (delta(p1.prefix, routenode) != 0 && delta (p2.prefix, routenode)!=0){
					node.get(routenode).prefixtable.get(delta(p1.prefix,routenode)).add(p1);
					node.get(routenode).prefixtable.get(delta(p2.prefix,routenode)).add(p2);
					//}
				}catch(Exception e){
					e.printStackTrace();
					if (node.get(routenode) == null){
						System.out.println("for "+routenode+"node.get(routenode) is null");
					}
					if (node.get(routenode).prefixtable == null){
						System.out.println("for "+routenode+"node.get(routenode).prefixtable is null");
					}
					if (node.get(routenode).prefixtable.get(delta(p2.prefix,routenode)) == null){
						System.out.println("For routenode: " + routenode + "for delta = "+delta(p2.prefix,routenode)+" prefix "+ p2.prefix+ " prefixstring: "+p2 +"node.get(routenode).prefixtable is null");
					}
					if (node.get(routenode).prefixtable.get(delta(p2.prefix,routenode)) == null){
						System.out.println("For routenode: " + routenode + "for delta = "+delta(p1.prefix,routenode)+" prefix "+ p1.prefix+ " prefixstring: "+p1 +"node.get(routenode).prefixtable is null");
					}
				}

				// now add the routing entry
				// derive this information from the "best" bucket
			
				Iterator<Prefix> prefix_it = node.get(routenode).prefixtable.get(delta(p1.prefix,routenode)).iterator();
				while (prefix_it.hasNext()){			
				
					Bucket best1 = new Bucket(best);
					//best1.dest = best.dest;
					best1.bucket_level = delta(routenode,best.dest);
					best1.nexthop = getNextHop(routenode, best.gw);
					best1.prefix =  prefix_it.next();
					// if dist(routenode, best.bridge[0]) > dist (routenode,best.bridge[1]) then its 
					// a bridge.
		
					/* 
					 * Who should be the gateway?? 
					 * TEMPORARILY I AM MAKING IT TO best.gw
					 */

					best1.gw = best.gw;
					node.get(routenode).buckets.add(best1);	
					/*
					 *  I SHOULD ANNOUNCE THIS NEW ROUTE TO MY RANDEZVOUS POINT TOO.
					 */
				node.get(routenode).publish(best1);
				}
			}
		}
		return options.isEmpty() == true?false:true;	
	}
	
	
	public int getCommonPrefixLen(long s1, long s2) {
		// TODO Auto-generated method stub
		int prefixlen = lbit;
		while ((s1 ^ s2) != 0){
			s1 = s1 >> 1;
				s2 = s2 >> 1;
		prefixlen--;
		}
		return prefixlen;
	}
	public Bucket getClosest(Set<Bucket> options, long src) {
		// it returns the bucket whose 'gateway' is the closest with respect to the 'src' node.
		Message msg = new Message();
		msg.type = Message.HOPCOUNT;
		msg.src = src;
		int hopcount = -1;
		Bucket b = new Bucket();
		Iterator <Bucket> it = options.iterator();
		while (it.hasNext()){
			Bucket c = it.next();
			msg.dest = c.gw;
			int hopc = routepacket(msg);
			println("Hopcount from "+msg.src + "->"+msg.dest+" = "+hopc, debug);
			if (hopc <0) {continue;}
			if ((hopcount >= hopc) || (hopcount == -1)){
				hopcount = hopc;
				b.copyFrom(c);
				println("New best option is: "+b,debug);
			}
		}
		println("Returning best option: "+b,debug);
		return b;
	}

	public Bucket getLogicallyClosest(Set<Bucket> options, long src) {
		// it returns the bucket whose 'gateway' is the closest with respect to the 'src' node.
		int logicalDistance = -1;
		Bucket b = new Bucket();
		Iterator <Bucket> it = options.iterator();
		while (it.hasNext()){
			Bucket c = it.next();
			int dist = delta (src,c.gw);
			//if (b.bucket_level >= 17 && (src == 2539520 || src == 2527232)) println("Logically distance from "+ src + "->"+c.gw+" = "+dist, true);
			if (dist <0) {
				System.out.println("Warning: Negative Logical distance!!\nLogically distance from "+ src + "->"+c.gw+" = "+dist);
				continue;
			}
			if ((logicalDistance >= dist) || (logicalDistance == -1)){
				logicalDistance = dist;
				b.copyFrom(c);
				println("New best option is: "+b,debug);
			}
		}
		//if (b.bucket_level >= 17 && (src == 2539520 || src == 2527232)) println("Returning best option for src: "+ src + " : "+b,true);
		return b;
	}

	public long getNextHop(long src, long dest) {
		// This function selects "any" of the next logical node and returns the corresponding nexthop node id. 
		// 
		if (src == dest){
			println("I am already at the destination. src = "+src + " dest = "+dest,debug);
		}
		long next = -1;
		int dist = delta(src,dest);
		Set<Bucket> options = node.get(src).buckets.get(dist);
		Bucket b = longestPrefixMatch(options,dest);
		//println("\n for src: "+src+"\tdest: "+dest+"LongestPrefixMatchBucket: "+b,debug);
		next = b.nexthop;
		return next;
	}

	public static Bucket longestPrefixMatch(Set<Bucket> options, long dest) {
		// this method will find the longest prefix match based destination bucket 
		Bucket b = new Bucket();
		Iterator<Bucket> it = options.iterator();
		while (it.hasNext()){
			Bucket c = it.next();
			if (b.dest == -1){
				b.copyFrom(c);
			}
			else if (delta(b.dest, dest) > delta(c.dest,dest)){
				b.copyFrom(c);
			}
		}
		return b;
	}
	public boolean query_new(Message msg, long currentnode) {
		boolean return_status = false;
		Set <Prefix> prefixes = node.get(currentnode).prefixtable.get(((Bucket)msg.payload).bucket_level);
		// clean the routing table of the querying node first
		node.get(msg.src).clearBucket(((Bucket)msg.payload).bucket_level);
		
		// Check for each prefix.. if prefix matches the ...
		Iterator <Prefix> it_prefix = prefixes.iterator();
		while (it_prefix.hasNext()){
			Prefix prefix = it_prefix.next();	
			// Now you have reached the "rendezvous point"
			Set <Bucket> options = new HashSet<Bucket>();
			
			// How prefixtable and rendev store are connected...
			for (Iterator<Bucket> it = node.get(currentnode).rendezvousStore.iterator(); it.hasNext();) {
				Bucket b1 = it.next();
				if (b1.bucket_level == ((Bucket)(msg.payload)).bucket_level && checkPrefix(b1.dest, prefix)){
					Bucket b = new Bucket(b1);
					//b.nexthop = node.get(msg.src).buckets[dist].nexthop;
					if (b.gw != msg.src){
						// if src not same as gateway then bucket's nexthop will be obtained by this method
						b.nexthop = getNextHop (msg.src,b.gw);
					}else{
						// if src itself is gateway then bucket's destination will be nexthop
						b.nexthop = b.dest;
					}
					//node.get(msg.src).buckets.add(b);
					options.add(b);
					//return true;
					println("Option added: "+b,debug);
					return_status = true;
				}
			}
			if (options.isEmpty() == false){
				// Now find the best matches:
				Bucket best = new Bucket();
				best.copyFrom(getLogicallyClosest(options,msg.src));	

				if (best.nexthop == -1){
					println("Nexthop is -1 for src: "+msg.src,debug);
				}
				println("For prefix: "+prefix+" Best option is: "+best,debug);
				// best.copyFrom(getOne(options));
				node.get(msg.src).buckets.add(best);
				/*if (msg.src == 10 && ((Bucket)(msg.payload)).bucket_level==4){
					System.out.println("Best is: "+best);
					System.out.println("New Routing Table is:\n "+node.get(msg.src).routing_table_toString());
				}*/					
				// update the prefix table
				node.get(msg.src).prefixtable.get(delta(msg.src, prefix.prefix)).add(prefix);
			}
		}	
		return return_status;
	}
	public boolean checkPrefix(long id, Prefix prefix) {
		// returns true if id is in the range of the prefix
		// else it returns false
		return (id >> (lbit-prefix.len)) == (prefix.prefix >> (lbit-prefix.len));
	}
	
	// Dead code
	public boolean query(Message msg, long currentnode) {

		// Now you have reached the "rendezvous point"
		for (Iterator<Bucket> it = node.get(currentnode).rendezvousStore.iterator(); it.hasNext();) {
			Bucket b1 = it.next();
			if (b1.bucket_level == ((Bucket)(msg.payload)).bucket_level){
				Bucket b = new Bucket(b1);
				//b.nexthop = node.get(msg.src).buckets[dist].nexthop;
				b.nexthop = getNextHop (msg.src,b.gw);
				//First remove the old entry, so that we can overwrite:
				//node.get(msg.src).buckets.get(b.)
				node.get(msg.src).buckets.add(b);
				return true;
			}
		}
		return false;
	}

	public boolean publish(Message msg, long currentnode) {
		//System.out.println("===> I am publishing the bucket:\n "+msg.payload);
		//if (node.get(currentnode).rendezvousStore.contains((Bucket) msg.payload) == false){
		println("===> I am publishing the bucket:\n "+msg.payload,debug);
		Bucket bb =  new Bucket ((Bucket) msg.payload);;
		bb.nexthop= -1;
		node.get(currentnode).rendezvousStore.add(bb);
		Prefix prefixset = ((Bucket)msg.payload).prefix;
		int bucketlevel = ((Bucket)msg.payload).bucket_level;
		node.get(currentnode).prefixtable.get(bucketlevel).add(prefixset);
		
		return true;
	}
	public static long getRdvVID(long vid, int k){
		/*
		 * computes the rendezvous point's id at for k'th level gateway for node vid
		 * 
		 * id is given by first l-(k-1) bits of vid, and by taking k-1 bits from hash(l-(k-1) bits of vid) 
		 */
		long rdv_vid=0;
		long mask = 1; // 0000 0001 (say k = 4)
		mask = mask << (k-1); // 00001000
		mask = mask -1;// 00000111
		mask = ~mask; // 11111 000
		long prefix = vid & mask;

		// now compute the hashed part.
		long hashval = ((long)((Long.toBinaryString(prefix<<32)).hashCode()))<<32 ;
		// System.out.println("hashval: "+ Long.toBinaryString(hashval));
		hashval = hashval+ ((long)(Long.toBinaryString(prefix)).hashCode());
		// System.out.println("hashval: "+ Long.toBinaryString(hashval));

		// hashval is 64 bit long, now only take last couple of bits from it, for this use the mask.
		// System.out.println("hashval: "+ Long.toBinaryString(hashval));
		hashval = hashval & (~mask);
		// System.out.println("hashval: "+ Long.toBinaryString(hashval));
		// System.out.println("SIZE of long: "+ Long.MAX_VALUE);

		// finally compute the rdv_vid using hashval and prefix
		rdv_vid = prefix + hashval;

		// System.out.println("Vid: "+ Long.toBinaryString(vid)+" Level = "+k+" Mask: "+Long.toBinaryString(mask)+ " Prefix: "+Long.toBinaryString(prefix)+" Hash val: "+Long.toBinaryString(hashval) + " RDV ID: "+Long.toBinaryString(rdv_vid));
		return rdv_vid;
	}

	public static String toBinaryString(long number){
		/*
		 * This function converts a number into a string of bits.
		 */
		if (number < 0){
			return "Nil";
		}
		return Long.toBinaryString( number);
	}

	public static int delta(long vid1,long vid2){
		if (vid1 < 0 || vid2 < 0){
			System.out.println("Negative vids!! "+vid1+ ' '+ vid2);
			return -1;
		}
		/*
		 * This functions computes the logical distance between vid1 and vid2 
		 */	
		// first compute the common prefix length:
		int dist=0;
		//System.out.println("Delta:  for  "+vid1+ " ["+Long.toBinaryString(vid1) +"], "+vid2+ " ["+Long.toBinaryString(vid2)+"]");
		while ((vid1 ^ vid2) != 0){
			dist++;
			vid1 = vid1>>1; vid2 = vid2>>1;
		//System.out.println(Long.toBinaryString(vid1) + ", " + Long.toBinaryString(vid2)  + "\t dist = " + dist);
		}
		return (dist);	
	}

	public void fillMinHopTable(String topofile, String options){

		/*
		 * EDGES WILL CONTAIN ALL THE EDGES FOR TOPOLOGY
		 */
		Vector<Edge> edges = new Vector<Edge>();
		/*
		 * NODELIST IS LIST OF ALL THE NODES
		 */
		nodeList = new ArrayList();
		
		String[] tok = new String[3];
		String line = new String();
		int maxNodeId = -1, temp;

		/*
		 * DATAINPUT STREAM HANDLE
		 * -G OPTION INDICATE BACKWARD COMPATIBILITY
		 * BELLMANFORD ASSUMES THAT TOPOLOGY FILE SHOULD BE:
		 * <NUMBER OF NODE>
		 * VERETX1 VERTEX2 WEIGHT
		 * VERTEX1 VERTEX3 WEIGHT 
		 * 
		 * HERE VERTEX STARTS FROM 0....(N-1)
		 */
		try{
			DataInputStream dis = new DataInputStream(new FileInputStream(topofile));
			if (options.equals("-g")){
				dis.readLine();
			}	
			Random generator = new Random();
			//Date d = new Date();
			//long time = System.currentTimeMillis();
			System.out.println("Seed time value is:"+seed);
			generator.setSeed((long) seed);


			while ((line = dis.readLine()) != null){
				/*
				 * DROPPING PACKETS RANDOMLY
				 */ 
				if (generator.nextFloat() < fracDrop){
					continue;
				}	
				/*
				 * SPLIT LINE ON SPACES
				 */
				tok = line.split(" ");
				if (options.equals("-g")){
					/*
					 * FOR -G OPTIONS ASSUMES WEIGHT TO BE 1
					 */
					edges.add(new Edge(Integer.parseInt(tok[0]) - 1, Integer.parseInt(tok[1]) - 1, 1));
					edges.add(new Edge(Integer.parseInt(tok[1]) - 1, Integer.parseInt(tok[0]) - 1, 1));
					if (! nodeList.contains(Integer.parseInt(tok[0])-1)){
						nodeList.add(Integer.parseInt(tok[0])-1);
					}
					if (! nodeList.contains(Integer.parseInt(tok[1])-1)){
						nodeList.add(Integer.parseInt(tok[1])-1);
					}
					temp = ((Integer.parseInt(tok[0])-1) > (Integer.parseInt(tok[1])-1))?
							((Integer.parseInt(tok[0])-1)):(Integer.parseInt(tok[1])-1);	
							if (maxNodeId < temp )
								maxNodeId = temp;
				}else{
					/*
					 * ELSE TAKE THE VALUE SPECIFIED IN THE FILE
					 */
					edges.add(new Edge(Integer.parseInt(tok[0]), Integer.parseInt(tok[1]), Integer.parseInt(tok[2])));
					edges.add(new Edge(Integer.parseInt(tok[1]) , Integer.parseInt(tok[0]), Integer.parseInt(tok[2])));
					if (! nodeList.contains(Integer.parseInt(tok[0]))){
						nodeList.add(Integer.parseInt(tok[0]));
					}
					if (! nodeList.contains(Integer.parseInt(tok[1]))){
						nodeList.add(Integer.parseInt(tok[1]));
					}
					temp = ((Integer.parseInt(tok[0])) > (Integer.parseInt(tok[1])))?
							((Integer.parseInt(tok[0]))):(Integer.parseInt(tok[1]));	
							if (maxNodeId < temp )
								maxNodeId = temp;
				}	
			}
			println("size of arraylist " + nodeList.size(),debug);
			minHopTable = new int[maxNodeId+1][maxNodeId+1];
			path = new String[maxNodeId+1][maxNodeId+1];
			nodes_count = maxNodeId+1;
			
			Collections.sort(nodeList);
			println("nodelist: "+nodeList,true);
			/*
			 * CALL BELLMANFORD FOR EACH NODE IN NODELIST ....
			 */
			int i = 0;
			for (i = 0; i < nodeList.size(); i++){
				bellmanFord(edges, maxNodeId+1, (Integer)nodeList.get(i));
			}
			/*
			 * PRINT THE MINHOPTABLE FOR EACH NODE...
			 */
			for ( i = 0; i< nodeList.size(); i++){
				for (int j =0 ; j< nodeList.size(); j++)
					println("Distance between " + i + " and " + j + "is " + minHopTable[nodeList.get(i)][nodeList.get(j)] + "\n", debug);
			}
		}
		catch(FileNotFoundException fe){
			System.out.println("error here\n");
			fe.printStackTrace();
		} catch (IOException ie){
			System.out.println();
			ie.printStackTrace();
		}
	}

	public void bellmanFord(Vector<Edge> edges, int nnodes, int source) {
		// the 'distance' array contains the distances from the main source to all other nodes
		int[] distance = new int[nnodes];

		for (int i = 0 ; i < nnodes; i++){
			path[source][i] = new String("");
		}

		//initially set - all distances are initiated to infinity
		Arrays.fill(distance, INF);
		// the distance from the main source to itself is 0
		distance[source] = 0;
		// in the next loop we run the relaxation 'nnodes' times to ensure that
		// we have found new distances for ALL nodes
		for (int i = 0; i < nnodes; ++i)
			// relax every edge in 'edges'
			for (int j = 0; j < edges.size(); ++j) {
				// analyze the current edge (SOURCE == edges.get(j).source, DESTINATION == edges.get(j).destination):
				// if the distance to the SOURCE node is equal to INF then there's no shorter path from our main source to DESTINATION through SOURCE
				if (distance[edges.get(j).source] == INF) continue;
				// newDistance represents the distance from our main source to DESTINATION through SOURCE (i.e. using current edge - 'edges.get(j)')
				int newDistance = distance[edges.get(j).source] + edges.get(j).weight;
				// if the newDistance is less than previous shortest distance from our main source to DESTINATION
				// then record that new shortest distance from the main source to DESTINATION
				if (newDistance < distance[edges.get(j).destination]){
					path[source][edges.get(j).destination] = path[source][edges.get(j).source] +" " + Integer.toString((edges.get(j).source));
					distance[edges.get(j).destination] = newDistance;
				}
			}
		// next loop analyzes the graph for cycles
		for (int i = 0; i < edges.size(); ++i)
			// 'if (distance[edges.get(i).source] != INF)' means:
			// "
			//	if the distance from the main source node to the DESTINATION node is equal to infinity then there's no path between them
			// "
			// 'if (distance[edges.get(i).destination] > distance[edges.get(i).source] + edges.get(i).weight)' says that there's a negative edge weight cycle in the graph
			if (distance[edges.get(i).source] != INF && distance[edges.get(i).destination] > distance[edges.get(i).source] + edges.get(i).weight) {
				System.out.println("Negative edge weight cycles detected!");
				return;
			}
		// this loop outputs the distances from the main source node to all other nodes of the graph
		for (int i = 0; i < distance.length; ++i)
			if (distance[i] == INF){
				println("There's no path between " + source + " and " + i, debug);
				minHopTable[source][i] = distance[i];
			}
			else{
				println("The shortest distance between nodes " + source + " and " + i + " is " + distance[i],debug);
				minHopTable[source][i] = distance[i];
			}

		for (int i = 0; i < nnodes; ++i){
			println("Path from"+ source +" to " + i + "is as this:" + path[source][i],debug);
		}
	}

	public void getConfiguration(String configfile){
		try {
			BufferedReader input = new BufferedReader(new FileReader(configfile));
			String line  = null;
			line = input.readLine();
			String property = "";
			String value = "";
			while (line != null){
				line = line.trim();
				if (line.startsWith("#") || line.length() < 3){
					line = input.readLine();
					continue;
				}
				int loc = -1;
				if ((loc = line.indexOf("=")) > 0){
					property = line.substring(0, loc);
					property = property.trim();
					value = line.substring(loc+1);
					value = value.trim();

					if (property.compareTo("computeStretch") == 0){	if (value.compareTo("false")==0){computeStretch = false;}	else{	computeStretch = true;	}	}
					else if (property.compareTo("recordPairWisePaths") == 0){	if (value.compareTo("false")==0){recordPairWisePaths = false;}	else{	recordPairWisePaths = true;	}	}
					else if (property.compareTo("recordRoutingTables") == 0){	if (value.compareTo("false")==0){recordRoutingTables = false;}	else{	recordRoutingTables = true;	}	}
					else if (property.compareTo("recordRoutingTables_ospf") == 0){	if (value.compareTo("false")==0){recordRoutingTables_ospf = false;}	else{	recordRoutingTables_ospf = true;	}	}
					else if (property.compareTo("recordPairWisePaths_ospf") == 0){	if (value.compareTo("false")==0){recordPairWisePaths_ospf = false;}	else{	recordPairWisePaths_ospf = true;	}	}
					else if (property.compareTo("recordControlPacketCount") == 0){	if (value.compareTo("false")==0){recordControlPacketCount = false;}	else{	recordControlPacketCount = true;	}	}
					else if (property.compareTo("countPackets") == 0){	if (value.compareTo("false")==0){countPackets = false;}	else{	countPackets = true;	}	}
					else if (property.compareTo("fillMinHopTable_run") == 0){	if (value.compareTo("false")==0){fillMinHopTable_run = false;}	else{	fillMinHopTable_run = true;	}	}
					else if (property.compareTo("run_viro") == 0){	if (value.compareTo("false")==0){run_viro = false;}	else{	run_viro = true;	}	}					
					else if (property.compareTo("plottopology") == 0){	if (value.compareTo("false")==0){plottopology = false;}	else{	plottopology = true;	}	}
					else if (property.compareTo("run_lsa") == 0){	if (value.compareTo("false")==0){run_lsa = false;}	else{	run_lsa = true;	}	}
					else if (property.compareTo("debug") == 0){	if (value.compareTo("false")==0){debug = false;}	else{	debug = true;	}	}
					else if (property.compareTo("fracDrop") == 0){	fracDrop = Float.parseFloat(value);}
					else if (property.compareTo("seed") == 0){	seed = Double.parseDouble(value);	}
					else {
						println("Config File = " + configfile+": No match found for value: "+ property + " and the value: "+value + " on line: " + line, true);
					}
				}
				line = input.readLine();
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}

		// print the configuration:
		println("-----> THE CONFIUGRATION <-----",true);
		println("\tcomputeStretch =  " + computeStretch , true);
		println("\trecordPairWisePaths =  " + recordPairWisePaths , true);
		println("\trecordRoutingTables =  " + recordRoutingTables , true);
		println("\trecordRoutingTables_ospf =  " + recordRoutingTables_ospf , true);
		println("\trecordPairWisePaths_ospf =  " + recordPairWisePaths_ospf , true);
		println("\trecordControlPacketCount =  " + recordControlPacketCount , true);
		println("\tcountPackets =  " + countPackets , true);
		println("\tfillMinHopTable_run =  " + fillMinHopTable_run , true);
		println("\trun_viro =  " + run_viro , true);
		println("\tplottopology =  " + plottopology , true);
		println("\trun_lsa =  " + run_lsa , true);
		println("\tdebug =  " + debug , true);
		println("\tfracDrop =  " + fracDrop , true);
		println("\tseed =  " + seed , true);
		//System.exit(0);
	}
	public void Measure_LSAload(){
		// Start Process
		boolean send = false;
		countLSA = new Hashtable<Integer, Integer>();
		lsa_receipt = new Hashtable<Integer, ArrayList<Integer>>();
		for (int i =0 ; i < nodeList.size(); i++){
			send  = false;
			for (int j =0; j < nodeList.size() ; j++){
				
				if (minHopTable[nodeList.get(i)][nodeList.get(j)] == 1){
					send = true;
					sendLSA(nodeList.get(i),nodeList.get(i), nodeList.get(j));
				}
			}
			if (send ){
				if (countLSA.get(nodeList.get(i)) == null)
					countLSA.put(nodeList.get(i), 1);
				else
					countLSA.put(nodeList.get(i), countLSA.get(nodeList.get(i))+1 );
			}
		}               
	}       
	
	public void sendLSA(int sender, int forwarder, int receive){
		
		if (lsa_receipt.get(receive) == null)
			lsa_receipt.put(receive, new ArrayList<Integer>());
		
		if (countLSA.get(receive) == null)
			countLSA.put(receive, 0);
		
		if (lsa_receipt.get(receive).contains(sender)){
			countLSA.put(receive, countLSA.get(receive)+1);
		}else{
			countLSA.put(receive, countLSA.get(receive)+1);
			lsa_receipt.get(receive).add(sender);
			for(int i =0 ; i< nodeList.size(); i++){
                
				if (minHopTable[receive][nodeList.get(i)] == 1 && forwarder!=nodeList.get(i))
					sendLSA(sender, receive , nodeList.get(i));             
			}
		}
	}
	
	public void print_ctrlPckt(){
		
		System.out.println("Node Info");
		
		Iterator<Integer> it = countLSA.keySet().iterator();
		while (it.hasNext()) {
			// Get value
			int key = it.next();
			System.out.println("Load on the node "+ key + " is " +countLSA.get(key));
		}
	} 
}


/* Sample configuration file:

# this is a comment 
computeStretch=false
# true will compute the stretch for all the possible pairs. look for .stretch file in the output

recordPairWisePaths=false
# true will record the pair wise paths. look for .paths file

recordRoutingTables=true
# true will record the routing tables, look for the .rt file in the output

recordRoutingTables_ospf=false
# true will record the routing tables for the ospf.

recordPairWisePaths_ospf=false
# true will record the pair wise paths for the ospf.

recordControlPacketCount=true
# set it to true if we want to measure the viro control overhead

countPackets=false
# set it to false if we want to measure the viro control overhead

fillMinHopTable_run=false
# true for the ospf based measurements, e.g. needed for routing stretch computation etc.

run_viro=true
# if you do not want to run the viro module set it to false

plottopology=false
# will plot the topology if set to true

run_lsa=false
# will run and count the "LSA" link state advertisements. 

fracDrop=0.0
# will drop the fraction of links

seed=0	
# seed value for the random number generator

# the values set in this file will be overridden by the conflicting values passed on the command line.

debug=false
# if it is true then lots of debug messages will also be printed




 */
